#ifndef _STACK_H_
#define _STACK_H_
 
#include <stdio.h>
#include <vector>
#include <map>
#include "atomic.h"
 
namespace utillib
{
	namespace util
	{
#ifdef          WIN32
#define                 TYPE_THREAD_ID                  DWORD
#define                 GET_THREAD_ID                   GetCurrentThreadId()
#define                 THREAD_LOCAL_STORAGE			  __declspec (thread)
#else
#define                 TYPE_THREAD_ID                  pthread_t
#define                 GET_THREAD_ID                   pthread_self()
#define                 THREAD_LOCAL_STORAGE			  __thread
#endif
		 
		struct StackElement
		{
			StackElement() : next( NULL ){};
			struct StackElement *next;
			void *value;
		};
		 
		typedef std::vector < StackElement * > stackElementList;
		 
		THREAD_LOCAL_STORAGE stackElementList *tls_hazardList = 0;
		 
		stackElementList *getHazardList();
		 
		template <typename _T_ >
		class Stack
		{
		public:
			Stack()
			{
				m_head.val64 = 0;
			}
		 
			virtual ~Stack()
			{
				clear();
			};
		 
			void push( _T_ value )
			{
				StackElement *element = createStackElement();
				element->value = ( void *)value;
		 
				for ( ;; )
				{
					element->next = m_head.val.element;
					if ( InterlockedCompareExchange( ( volatile long *)&( m_head.val.element ), ( long )element , ( long )element->next ) == ( long )element->next )
							break;
				}
			}
		 
			_T_ pop()
			{
				union UnionDouble head;
				for ( ;; )
				{
					head.val64 = m_head.val64;
					if ( head.val.element == NULL ) return ( 0 );
		 
					union UnionDouble next;
					next.val.element = head.val.element->next;
					next.val.count = head.val.count + 1;
		 
					if ( CAS64( ( volatile long long *)&m_head.val64, next.val64, head.val64 ) == head.val64 )
					{
						break;
					}
				}
		 
				StackElement *element = head.val.element;
				_T_ returnVal = ( _T_ )element->value;
		 
				releaseStackElement( element );
		 
				return returnVal;
			}
		 
		protected:
			union UnionDouble
			{
				struct
				{
					struct StackElement *element;
					int count;
				} val;
				long long val64;
			};
		 
		public:
			void clear()
			{
				for ( ;; )
				{
					_T_ object = pop();
					if ( object == 0 ) break;
				}
			}
		 
		protected:
			void removeAllMemory()
			{
				for ( ;; )
				{
					_T_ object = pop();
					if ( object == 0 ) break;
		 
					delete object;
				}
			}
		 
		protected:
			volatile union UnionDouble m_head;
		 
		 
		private:
			typedef typename stackElementList::const_iterator stackElementListConstIter;
		 
			StackElement *createStackElement()
			{
				StackElement *element = NULL;
		 
				stackElementList *elementList = getHazardList();
				if ( !elementList->empty() )
				{
					element = elementList->back();
					elementList->pop_back();
		 
					return ( element );
				}
				element = new StackElement;
				return ( element );
			}
		 
			void releaseStackElement( StackElement *element )
			{
				stackElementList *elementList = getHazardList();
				elementList->push_back( element );
			}
		};
		 
		class StackElementListStack : public Stack < stackElementList * >
		{
		public:
			StackElementListStack(){};
			virtual ~StackElementListStack()
			{
				for ( StackElement *element = m_head.val.element ; element ; element = element->next )
				{
					delete ( stackElementList *)element->value;
				}
		 
			};
		 
		};
		 
		stackElementList *getHazardList()
		{
			if ( tls_hazardList == NULL )
			{
				tls_hazardList = new stackElementList;
				static StackElementListStack s_selfStorage;
				s_selfStorage.push( tls_hazardList );
			}
			return tls_hazardList;
		};
	}
}

#endif
 
